﻿#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
#include "queue.h"

//利用数组中的数据来创建二叉树，数组中的数据为char类型
// 思路：遇#要返回null，#后面不能再链接结点了，和空一样
// 结点数据插入节点->数组逐步向后遍历->左右孩子
//BTNode* CreatBinaryNode(char* arr, int* pi)
//{
//	if (arr[(*pi)] == '#')
//	{
//		(*pi)++;
//		return NULL;
//	}
//	BTNode* root = BuyNode(arr[(*pi)]);
//	(*pi)++;
//	root->left = BuyNode(arr[(*pi)]);
//	root->right = BuyNode(arr[(*pi)]);
//
//	return root;
//}

//前序遍历--根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)//递归结束条件
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历--左根右
void InOrder(BTNode* root)
{
	if (root == NULL)//递归结束条件
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

//后序遍历--左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

// ⼆叉树结点个数（根结点+左子树+右子树）
//int size = 0;
//int BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	++size;
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//	return size;//这样只能保证第一次打印的结果是正确的，
//	//如果再次打印，就会造成结果翻倍，就会stactic关键字也是同理的，这是错误的,这里的全局变量和局部变量都不行,所以我size直接写在test.c文件中
//}
// 这里需要对同一个地址的size自增，函数递归会一直创建size，不取地址的话，size始终为1
//void BinaryTreeSize(BTNode* root,int* psize)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	++(*psize);
//	BinaryTreeSize(root->left, psize);
//	BinaryTreeSize(root->right, psize);
//}
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//根结点+左子树+右子树
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

// ⼆叉树叶⼦结点个数（左子树叶子结点个数+右子树叶子结点个数）
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// ⼆叉树第k层结点个数(向下遍历时，k--，当k==1时,就是第k层)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;//能够走到k==1的层次，说明这个结点一定存在，反之也许在k==2是就NULL返回了
	}//或者这条线我都能走到第k层，说明这条线在k层一定有路径
	return BinaryTreeLevelKSize(root->left, k - 1) 
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

//⼆叉树的深度/⾼度(根节点+max（左子树，右子树）)
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
	return 1 + (leftDep > rightDep ? leftDep : rightDep);
}//三目操作符

//⼆叉树查找值为x的结点(查找左子树和右子树)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	//这个结点是空，没有找到
	if (root == NULL)
	{
		return NULL;
	}
	//这个结点找到了
	if (root->data == x)
	{
		return root;
	}
	//继续向左子树寻找
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	//继续向右子树寻找
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	//没找到
	return NULL;
}

// ⼆叉树销毁（形参需要改变实参，传的是二级指针）
// 可以为了保持接口一致性，可以改为一级指针，最后手动将根结点销毁
//每一个申请的结点都要销毁，仍然需要遍历，不能一开始销毁根结点，否则后面的结点就找不到了
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));//(&(*root->left))这样写的话->优先级比*高，我们需要添加一个（）
	BinaryTreeDestory(&((*root)->right));//(&(*root->right))这样写的话->优先级比*高，我们需要添加一个（）
	free(*root);
	*root = NULL;
}


//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))//是空孩子的话就直接出循环了，所以要非空孩子
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", top->data);
		//将队头结点的非空左右孩子结点入队列
		if (top->left)
			QueuePush(&q,top->left);
		if (top->right)
			QueuePush(&q,top->right);
	}
	QueueDestroy(&q);
}


//判断是否为完全二叉树
//注意:这个phead是队列的头节点，如果他为空，那么说明队列是空了；
// 而咱们的那个NULL，是代表我们存的队列节点中的那个元素值
//也就是我们队列本身存int的元素类型，现在存的是树节点指针类型
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;//只能是碰到这个条件之后才能退出循环
		}
		//左右孩子入队列
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//队列不为空，继续取队头出队头
	//队列存在非空节点--非完全二叉树
	//队列不存在非空结点--完全二叉树
	while (!QueueEmpty(&q))//这里与Queue判断队头是否为空不同，Queue与结点一个一个相互联系，判断只是判断一个头结点
	{//而此处判空可以把队列里面所有元素看成头结点（开学问一下学长）
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}